package LinkedList;

public class _234_PalindromeLinkedList {
    //可行，超时
    public boolean isPalindrome0(ListNode head) {
        ListNode p = head;
        String s = "";
        String reverseS = "";
        while(p!=null){
            s += p.val;
            reverseS+= new StringBuffer(p.val+"").reverse().toString();
            p = p.next;
        }
        return s.equals(new StringBuffer(reverseS).reverse().toString());
    }

    //仍旧超时
    public boolean isPalindrome1(ListNode head) {
        ListNode p = head;
        String s = "";
        StringBuffer SB = new StringBuffer(s);
        StringBuffer reverseSB = new StringBuffer(s);
        while(p!=null){
            int val = p.val;
            SB.append(val);
            reverseSB.insert(0,val);
            p=p.next;
        }
        return SB.toString().equals(reverseSB.toString());
    }


    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null) return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast.next!=null){
            slow = slow.next;//set slow to the middle
        }
        ListNode secondA = head;
        ListNode secondB = slow.next;

        slow = reverse(slow);
        fast = head;
        while(slow!=null){
            if(slow.val!=fast.val){
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    //反转后半部分的链表
    public ListNode reverse(ListNode node){
        ListNode prev = null;
        while(node!=null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
}
